package dvonn.ai;

import java.awt.Point;
import java.util.ArrayList;

import dvonn.game.GameField;
import dvonn.game.Move;
import dvonn.game.Token;

public class Solver {
	
	private int testedMoves;
	private int maxTestedMoves;
	
	public Move getMove(GameField game, Token me, int maxMoves) {
		maxTestedMoves = maxMoves;
		testedMoves=0;
		DvonnTree solveTree = new DvonnTree(null);
		solve(solveTree, game, me, me);
		DvonnTree bestChild=null;
		System.out.print("All (computed) possible moves : ");
		ArrayList<DvonnTree> allChilds = solveTree.gettAllChilds();
		bestChild = allChilds.get(0);
		for (DvonnTree child: allChilds) {
			if ( bestChild.getValue() < child.getValue() ) {
				bestChild = child;
			}
			System.out.print(child.getMove()+"="+child.getValue()+"("+bestChild.getValue()+") ");
		}
		System.out.println("\n"+testedMoves+" tested moves");
		System.out.println("best move result : "+bestChild.getValue());
		return bestChild.getMove();
	}

	private int solve(DvonnTree tree, GameField game, Token player, Token me) {
		if (testedMoves<maxTestedMoves) {
			ArrayList<Move> possibleMoves = new ArrayList<Move>();
			
			// Liste alle moeglichen Moves erstellen
			ArrayList<Point> sources = game.getAllMovable(player);
			while (!sources.isEmpty()) {
				ArrayList<Point> targets = game.getAllValidTargets(sources.get(0));
				for (Point target : targets) {
					possibleMoves.add(new Move(sources.get(0),target));
				}
				sources.remove(0);
			}
			
			// es sind Moves moeglich
			if (!possibleMoves.isEmpty()) {
				//System.out.print("("+possibleMoves.size()+")");
				for (Move move : possibleMoves) {
					if (testedMoves<maxTestedMoves) {
						// cutoff
						if (tree.valueInited()) {
							if (player==me) {
								if (tree.getParent()!=null) {
									if (tree.getParent().valueInited()) {
										if (tree.getValue()>tree.getParent().getValue()) {
											//System.out.print("cut ");
											return tree.getValue(); 
										}
									}
								}
							} else {
								if (tree.getParent()!=null) {
									if (tree.getParent().valueInited()) {
										if (tree.getValue()<tree.getParent().getValue()) {
											//System.out.print("cut ");
											return tree.getValue(); 
										}
									}
								}
							}
						}
						// ohne cutoff
						testedMoves++;
						DvonnTree child = new DvonnTree(tree);
						child.setMove(move);
						tree.addChild(child);
						GameField newGame = new GameField(game);
						newGame.doMove(move.getSource(), move.getTarget());
						int childValue = solve(child, newGame, player.nextPlayer(), me);
						if (!(tree.valueInited())) {  // erstes untersuchtes Kind
							tree.setValue(childValue);
							if (tree.getParent()!=null) {  // durchreichen zu Eltern
								if (!tree.getParent().valueInited()) {
									tree.getParent().setValue(childValue);
								}
							}

		 					//System.out.print("-");
						} else {
							if (player == me) {
								if (tree.getValue() < childValue) {
									//System.out.print("+");
									tree.setValue(childValue);
								}
							} else {
								if (tree.getValue() > childValue) {
									//System.out.print("+");
									tree.setValue(childValue);
								}
							}
							
						}
					}
				}
				
			} else { // keine Moves moeglich
				if (tree.getParent()!=null) {
					if (tree.getParent().getMove()==null) { // 2. mal aussetzen -> Spielende
	 					int[] results = game.getScore(new Token[] { me, me.nextPlayer()} );
	 					int score = results[0]-results[1];
	 					tree.setValue(score);
	 					//System.out.print(score+", ");
	 					return score;
					} else {  //aussetzen
						testedMoves++;
						DvonnTree child = new DvonnTree(tree);
						tree.addChild(child);
						tree.setValue( solve(child, game, player.nextPlayer(), me) );
	 					//System.out.print("["+tree.getValue()+"]");
					}
				} else { // aussetzen bei spielstart :P
					testedMoves++;
					DvonnTree child = new DvonnTree(tree);
					tree.addChild(child);
					tree.setValue( solve(child, game, player.nextPlayer(), me) );
 					//System.out.print("["+tree.getValue()+"]");
				}
			}
			
		} else { tree.setValue(Integer.MIN_VALUE); }  // Zeitkriterium
		
		return tree.getValue();
	}

}
